#pragma once

#include "TypeDefin.h"

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;

/*HJJ QQ479287006
 *
 * */
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
    if (preorder.size() == 0)
        return nullptr;

    ////确定根节点
    int root = preorder[0];
    TreeNode *node = new TreeNode(root);
    int index = 0;
    for (index = 0; index < inorder.size(); index++) {
        if (inorder[index] == root)
            break;
    }

    vector<int> inorderLeft = vector(inorder.begin(), inorder.begin() + index);
    vector<int> inorderRight = vector(inorder.begin() + index + 1, inorder.end());


    vector<int> preorderLeft = vector(preorder.begin() + 1, preorder.begin() + inorderLeft.size() + 1);
    vector<int> preorderRight = vector(preorder.begin() + 1 + inorderLeft.size(), preorder.end());

    node->left = buildTree(preorderLeft, inorderLeft);
    node->right = buildTree(preorderRight, inorderRight);

    return node;

}